Motivation

What is the PAC framework?

近似解を達成するために必要なサンプル点の数、サンプルの複雑さ、学習アルゴリズムの時間と空間の複雑さの観点から、学習可能な概念のクラスを定義するのに役立つ（これは概念の計算表現のコストに依存する）

最初にPACフレームワークを説明・例示し、使用される仮説集合が学習する概念を含む一貫性のあるケースと一貫性のないケースの両方で、使用される仮説集合が有限である場合に、このフレームワーク内のいくつかの一般的な学習保証を提示する

Definitions and Notation

What is the task?

  • ラベル付けされた標本\(S\)を用いて、概念\(c\)に関して一般化誤差が小さい仮説\(h∈\mathcal{H}\)を選択すること

Errors

Definition 2.1 (Generalization error)

ターゲット概念\(c\in \mathcal{C}\)とターゲット分布\(\mathcal{D}\)が与えられたときの、仮説\(h \in \mathcal{H}\)の汎化誤差orリスクは次のように定義される。ここで\(1_{\omega}\)はイベント\(\omega\)の指示関数。

\[ R(h) = Pr_{x \sim \mathcal{D}}[h(x) \neq c(x)] = \mathbb{E}_{x \sim \mathcal{D}}[1_{h(x) \neq c(x)}] \tag{2.1} \]

  • この定義と他の関連する定義のために、関数\(\mathcal{H}\)とターゲット概念\(c\)は測定可能でなければならない。

  • 仮説の汎化誤差は、分布\(\mathcal{D}\)とターゲット概念\(c\)の両方が未知であるため、学習者が直接知ることはできない。

  • しかし、学習者はラベル付けされた標本\(S\)上で仮説の経験誤差を測定することができる。

Definition 2.2 (Empirical error)

仮説\(h \in \mathcal{H}\)、ターゲット概念\(c\in \mathcal{C}\)、標本\(S = (x1, ... , xm)\)が与えられると、仮説\(h\)の経験誤差または経験リスクは以下で定義される。

\[ \hat{R_S}(h) = \frac{1}{m}\sum^{m}_{i = 1}1_{h(x) \neq c(x)} \tag{2.2} \]

  • \(h \in \mathcal{H}\)の経験誤差は標本\(S\)における\(h\)の平均誤差

  • 一般化誤差は分布\(D\)に基づくその期待誤差

  • i.i.d.標本\(S\)に基づく経験誤差の期待値は汎化誤差に等しい (経験誤差は汎化誤差の不偏推定量)

\[ \mathbb{E}_{S \sim \mathcal{D}^m}[\hat{R_S}(h)] = R(h) \tag{2.3} \]

proof

PAC model

Definition 2.3 (PAC-learning)

  • 以下のような学習アルゴリズム\(\mathcal{A}\)が存在するとき、概念クラス\(\mathcal{C}\)はPAC学習可能(PAC-learnable)である

    • 固定多項式に対する大きさ\(m = poly(1/\epsilon, 1/\delta)\)の標本\(S\)
    • 任意のターゲット概念\(c \in \mathcal{C}\),\(\epsilon > 0\),\(\delta > 0\)およびすべての分布\(\mathcal{D}\)について、

\[ Pr_{S \sim \mathcal{D}^m}[R(h_S) \leq \epsilon] \geq 1 - \delta \tag{2.4} \]

Remarks

  • PAC フレームワークはdistribution-free モデル (分布の仮定なし)

  • 誤差を定義するために使用される学習サンプルとテスト例は、同一の分布\(\mathcal{D}\)に従う

  • パラメータ\(\delta > 0\)は信頼度\(1 - \delta\)を、\(\epsilon > 0\)は精度\(1 - \epsilon\)を求めるために使用

  • 概念クラス\(\mathcal{C}\)はアルゴリズムにとって既知であるが、ターゲット概念\(c \in \mathcal{C}\)は未知であることに注意

Example (Rectangles Learning)

Guarantees for finite hypothesis sets — consistent case

Theorem 2.5 (Learning bound — finite H, consistent case)

  • \(\mathcal{H}\)を\(\mathcal{X}\)から\(\mathcal{Y}(\{0,1\})\)に写像する関数の有限集合とする

  • \(\mathcal{A}\)は、任意のターゲット概念\(c \in \mathcal{H}\)とi.i.d.標本\(S\)に対して、一貫性のある仮説\(h_S\)(\(\hat{R}_S(h_S) = 0\))を返すアルゴリズムとする

  • 任意の\(\delta > 0\)に対して、少なくとも\(1-\delta\)の確率で

\[ R(h_S) \leq \frac{1}{m}(log|\mathcal{H}| + log \frac{1}{\delta}) \tag{2.9} \]

proof

Example 2.6 (Conjunction of Boolean literals)

Boolean : true or falseの型 (java?)
literals: 定数値

以下では、Boolean literalsを「ブール値」と訳す

  • 最大n個のブール値 \(x_1, ... , x_n\) の論理積の概念クラス\(\mathcal{C}_n\)を学習することを考える

    • ブール値は、変数 \(x_i, \; i ∈[n]\)、またはその否定 \(\bar{x}_i\) のいずれか

  • 例1）n = 4

    • 論理積 \(x_1∧ \bar{x}_2∧ x_4\) があり、ここで \(\bar{x}_2\) はブール値 \(x_2\) の否定を表す

    • (1, 0, 0, 1) はこの概念の正の例

    • (1, 0, 0, 0) はこの概念の負の例

  • 例2）n = 4

    • 正の例 (1, 0, 1, 0) は、ターゲット概念が定数値 \(\bar{x}_1\) と \(\bar{x}_3\) を含むことができず、定数値 \(x_2\) と \(x_4\) を含むことができないことを意味する

    • 対照的に、負の例 (例えば(1,0,0,0)) はそのnビットのうちのどのビットが正しくないかがわからないため、情報量が少なくなる

  • よって一貫性のある仮説を見つけるための簡単なアルゴリズムは、正の例に基づいており、次のように構成されています。

    • 各正の例 \((b_1, ... , b_n)\) と \(i∈[n]\) について、
      \(b_i=1\)ならば、\(x_i\)は概念クラスの可能性のある定数値とされ、
      \(b_i=0\)ならば、\(x_i\)は除外される

    • 除外されていないすべての定数値の論理積は、ターゲット概念と一致する仮説となる

Example Figure2.4

  • 以下の図2.4は、学習サンプルの例と、n = 6の場合の一貫した仮説を示している

  • 図2.4 (n = 6のとき)

    • 表の最初の6行は学習例

    • 最後の列 (7列目) に\(+\)または\(-\)のラベル

    • 最後の行 (7行目) は、すべての正の例 (7列目が\(+\)) に対して、\(i\)列目の要素が全て0(or1)であれば、\(i∈[6]\)にそれぞれ0(or1)が入る

    • また、正の例において、0と1の両方が\(i\)番目の要素として現れる場合 (図中の赤枠) には、最後の行に“?”が入る

    • この学習サンプルについて、一貫性のあるアルゴリズムによって返される仮説は、\(\bar{x}_1∧ x_2∧ x_5∧ x_6\)

Algorithm

  • 各ブール値は正に含まれていても、否定されていても、含まれていなくてもよいので、
    \(|\mathcal{H}| =|\mathcal{C}n| = 3^n\)となる

  • 一貫性のある仮説の標本複雑度境界(式2.8)に当てはめると、任意の \(\epsilon > 0\) および \(\delta > 0\) において、
    以下のような標本複雑度境界が得られる

\[ m \geq \frac{1}{\epsilon}\bigl( (log3)n \:+\: log\frac{1}{\delta} \bigr) \tag{2.10} \]

  • したがって，最大n個のブール値の論理積のクラスはPAC-learnableである

    • (2.10)を満たすならば、仮説 \(h_S\) は任意の \(\epsilon,\delta > 0\) に対して、\(Pr_{S \sim D^m}[R(h_s) \leq \epsilon] \geq 1 - \delta\) を満たす。すなわちPAC-learnablである。

  • \(δ = 0.02、\epsilon = 0.1、n = 10\)の場合、境界は\(m \geq 149\)となる

    • 少なくとも149個の例のラベル付きサンプルでは、この境界は、少なくとも98%の信頼度で90%の精度を保証

Guarantees for finite hypothesis sets — inconsistent case

Corollary 2.10

Corollary: ある主張（典型的には定理）の系（けい、英: corollary）とは、その（既知の）主張から「直ちに」証明される主張をいう (Wikipediaより引用)

  • \(\epsilon>0\) とすると、任意の仮説 \(h : X → \{0, 1\}\) に対して，次の不等式が成立する

\[ Pr_{S \sim D^m}[\hat{R}_S(h)-R(h) \geq \epsilon] \leq exp(-2m\epsilon^2) \tag{2.14} \] \[ Pr_{S \sim D^m}[\hat{R}_S(h)-R(h) \leq -\epsilon] \leq exp(-2m\epsilon^2) \tag{2.15} \]

  • プールの不等式により、以下のような両面不等式を意味する

\[ Pr_{S \sim D^m}[|\hat{R}_S(h)-R(h)| \geq \epsilon] \leq 2exp(-2m\epsilon^2) \tag{2.16} \] ### proof

  • この結果は定理D.2からすぐに従う

Corollary 2.11 (Generalization bound — single hypothesis)

系 2.11 (一般化境界-単一仮説)

  • 仮説 h をX → {0, 1}とすると、任意の\(δ＞0\)に対して、以下の不等式が少なくとも\(1 - δ\)の確率で成り立つ

\[ R(h) \leq \hat{R}_S(h) \:+\: \sqrt{\frac{log2/\delta}{2m}} \tag{2.17} \]

Example 2.12 (Tossing a coin)

  • 偏ったコインを投げて、確率\(p\)で表が出ると想像

    • 我々の仮説:常に裏を推測するものとする

  • 真の誤差確率は\(R(h) = p\)、経験誤差確率は\(\hat{R}_S(h) = \hat{p}\)

    • ここで\(\hat{p}\)はi.i.dに抽出された学習サンプルに基づいた、表が出る経験的な確率

  • このように，系2.11は，少なくとも\(1 - δ\) の確率で，以下を保証する

\[ |p-\hat{p}| \leq \sqrt{\frac{log2/\delta}{2m}} \tag{2.18} \]

  • したがって、\(δ＝0.02\)とし、大きさ\(m=500\)の標本を用いた場合、98％以上の確率で、次のような近似が保証される

\[ |p-\hat{p}| \leq \sqrt{\frac{log2(10)}{1000}} \approx 0.048 \tag{2.19} \]

  • 標本Sで学習したときに学習アルゴリズムによって返される仮説\(h_S\)の汎化誤差を抑えるために、系2.11を容易に適用できるだろうか？

    →\(h_S\) は固定された仮説 (fixed hypothesis) ではなく、抽出された訓練標本Sに依存するランダム変数であるため、系2.11を容易に適用できない

  • 経験誤差の期待値が汎化誤差（式 (2.3)）である固定された (fixed) 仮説の場合とは異なり、汎化誤差\(R(h_S)\)はランダム変数であり、一般的に定数である期待値\(\mathbb{E}[\hat{R}_S(h_S)]\)とは異なることにも注意

    →したがって、一貫した場合の証明と同様に一様収束境界、すなわちすべての仮説\(h∈\mathcal{H}\)に対して高い確率で保持される境界を導出する必要がある

Theorem 2.13 (Learning bound — finite H, inconsistent case)

  • \(\mathcal{H}\) を有限仮説集合とする

  • すると、任意の\(δ＞0\)について、少なくとも \(1 -δ\) の確率で、次の不等式が成立

\[ \forall h \in \mathcal{H},\; R(h) \leq \hat{R}_S(h) \: + \: \sqrt{\frac{log|\mathcal{H}|\: + \: log2/\delta}{2m}} \tag{2.20} \]

proof(Theorem 2.13)

Remarks

  • このように、ある有限の仮説集合 \(\mathcal{H}\) について、高い確率で(whp : with high probability)

\[ \forall h \in \mathcal{H},\;R(h) \leq \hat{R}_S(h) \: + \: O\sqrt{\frac{log_2|\mathcal{H}|}{m}} \]

  • \(log_2|\mathcal{H}|\)は\(\mathcal{H}\)を表現する(符号化する)のに必要なビット数として解釈できる

  • この境界は経験誤差の低減と仮説集合の大きさの制御との間のトレードオフを求めることを示唆

    • 仮説集合を大きくする(mを大きくする)と第2項でペナルティを受けるが，第1項である経験誤差の低減に役立つ可能性がある

    • 一方で同じような経験誤差の場合、より小さな仮説集合を使うことを示唆

→ Occam’s Razor principle (オッカムの剃刀の原理) の例

Occam’s Razor principle

「Plurality should not be posited without necessity」 (必要以上に多くを仮定すべきではない)

「the simplest explanation is best」(最も単純な説明が最善である) とも言い換えられる

  • 今回の文脈では、「他のすべてのものが等しいと、より単純な（より小さい）仮説集合がより良い」

Summary

\[ Pr_{S \sim \mathcal{D}^m}[R(h_S) \leq \epsilon] \geq 1 - \delta \]

\[ R(h) \leq \frac{1}{m}(log|\mathcal{H}|\:+\:log\frac{1}{\delta}) \]

\[ R(h) \leq \hat{R}_S(h)\:+\:\sqrt{\frac{log|\mathcal{H}|\: + \: log2/\delta}{2m}} \]